import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

    List<List<String>> res;
    int height;//表示树的高度
    public List<List<String>> printTree(TreeNode root) {
        height =  getTreeHeight(root);
        //初始化layer
        int n = (int) (Math.pow(2, height + 1) - 1);
        //初始化res
        res = new ArrayList<>(height + 1);

        for (int i = 0; i < res.size(); i++) {
            res.set(i, new ArrayList<>(n));
        }
        dfs(root,0, (n - 1) / 2);

        return res;
    }
    private void dfs(TreeNode node, int row, int col){
        if(node == null) return;
        res.get(row).set(col, Integer.toString(node.val));
        dfs(node.left, row + 1,col - (int)Math.pow(2,height - row - 1));
        dfs(node.left, row + 1,col + (int)Math.pow(2,height - row - 1));
    }
    private int getTreeHeight(TreeNode node){
        if(node == null) return 0;
        return Math.max(getTreeHeight(node.left), getTreeHeight(node.right)) + 1;
    }
}
